/**
 * 几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
 * <p>
 * 每次行动，你可以从行的**开头或者末尾**拿一张卡牌，最终你必须正好拿 k 张卡牌。
 * (由于只能从开头或末尾拿牌，所以最后剩下的牌必然是连续的。)
 * 你的点数就是你拿到手中的所有卡牌的点数之和。
 * <p>
 * 给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
 */

/**
 * 解法一：问题变成：
 * 计算长为 n−k 的连续子数组和的最小值。
 * 这可以用滑动窗口解决。
 */

class Solution {
    public int maxScore(int[] cardPoints, int k) {

        int totalSum = 0;
        int length = cardPoints.length - k;  //剩余子串长度
        for (int i = 0; i < length; i++) {
            totalSum += cardPoints[i];
        }

        int minWindowSum = totalSum;
        int windowSum = totalSum;

        for (int i = length; i < cardPoints.length; i++) {
            //0.计算元素的总和
            totalSum += cardPoints[i];
            windowSum += cardPoints[i] - cardPoints[i - length];//1.2.元素进入、弹出窗口
            //3.更新元素的最值.
            minWindowSum = Math.min(minWindowSum, windowSum);
            //3.元素弹出窗口.不能这样写
            //windowSum -= cardPoints[i - length];
        }
        return totalSum - minWindowSum;
    }

    /**
     * 方法二：正向思维
     * 答案等于如下结果的最大值：
     * <p>
     * 前 k 个数的和。
     * 前 k−1 个数以及后 1 个数的和。
     * 前 k−2 个数以及后 2 个数的和。
     * ……
     * 前 2 个数以及后 k−2 个数的和。
     * 前 1 个数以及后 k−1 个数的和。
     * 后 k 个数的和。
     */

    public int maxScore2(int[] cardPoints, int k) {

        int maxSum = 0;
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += cardPoints[i];
        }
        maxSum = windowSum;                 //1.初始化窗口和最值
        for (int i = 1; i <= k; i++) {      //2.滑动窗口的值要从1到k
            windowSum = windowSum + cardPoints[cardPoints.length - i] - cardPoints[k - i];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }


}